/**
 * 删除排序链表中的重复元素
 *
 * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
 *
 * 示例 1：
 * 输入：head = [1,1,2]
 * 输出：[1,2]
 *
 * 示例 2：
 * 输入：head = [1,1,2,3,3]
 * 输出：[1,2,3]
 *
 * 提示：
 * 链表中节点数目在范围 [0, 300] 内
 * -100 <= Node.val <= 100
 * 题目数据保证链表已经按升序 排列
 */

/**
 * 我们遍历一遍链表, 这题的细节点和 82 的一样, 记得将加入链表后面的链表值为空
 * 时间复杂度 : O(n)
 * 空间度咋读 : O(1)
 */

public class Main {
    public ListNode deleteDuplicates(ListNode head) {

        // 虚拟头结点
        ListNode newHead = new ListNode(0);
        newHead.next = head;

        // 初始话节点
        ListNode tmp = newHead;
        ListNode cur = head;
        ListNode prev = head;

        while (cur != null) {

            cur = cur.next;

            // 这里我们直接加入 链表就可以了
            // 只要将后面重复的数给排除掉就可以了
            tmp.next = prev;
            prev.next = null;
            tmp = prev;

            // 排除重复的元素
            while (cur != null && cur.val == prev.val) {
                cur = cur.next;
            }

            // 更新当前节点
            prev = cur;
        }

        // 返回
        return newHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}